package wtx.leetcode;

/**
 * Given an integer array nums, find the contiguous subarray (containing at
 * least one number) which has the largest sum and return its sum.
 * 
 * Example:
 * 
 * Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6
 * Explanation: [4,-1,2,1] has the
 * largest sum = 6. 
 *     candMax = input[0], sum = max(0, sum + input[i]) = 0
 *   i = 1:
 *     sum = 1, candMax = 1
 *     sum = 0, candMax = 1
 *     sum = 4, candMax = 4
 *     sum = 3, candMax = 4
 *     sum = 5, candMax = 5
 *     sum = 6, candMax = 6
 *     sum = 1, 
 *     sum = 5, 
 * Follow up:
 *   If you have figured out the O(n) solution, try coding another solution using
 * the divide and conquer approach, which is more subtle.
 */
public final class Solution {
  public int maxSubArray(int[] nums) {
    int candMax = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] > candMax) {
        candMax = nums[i];
      }
    }
    int sum = Math.max(0, nums[0]);
    for (int i = 1; i < nums.length; ++i) {
      sum = Math.max(0, nums[i] + sum);
      if (sum > 0 && sum > candMax) {
        candMax = sum;
      }
    }
    return candMax;
  }

  public static void main(String[] args) {
    int[] input = {-2,-1};//,-3,4,-1,2,1,-5,4};
    Solution s = new Solution();
    int maxSub = s.maxSubArray(input);
    System.out.println("max sub array = " + maxSub);
  }
}
